class Solution {
    /**
     * 滑动窗口+记录差距思想
     *
     * 使用diff变量记录curr数组和target数据的差距
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int len1 = s.length(), len2 = p.length();
        if (len1 < len2) {
            return ans;
        }

        int[] curr = new int[26];
        int[] target = new int[26];
        for (int i = 0; i < p.length(); i++) {
            target[p.charAt(i) - 'a']++;
            curr[s.charAt(i) - 'a']++;
        }

        // 记录差距
        int diff = 0;
        for (int i = 0; i < 26; i++) {
            diff += Math.abs(target[i] - curr[i]);
        }
        if (diff == 0)
            ans.add(0);

        // 更新差距
        for (int i = 1; i <= len1 - len2; i++) {
            int ch1 = s.charAt(i - 1) - 'a';
            int ch2 = s.charAt(i + len2 - 1) - 'a';
            diff -= Math.abs(target[ch1] - curr[ch1]);
            diff -= Math.abs(target[ch2] - curr[ch2]);
//            System.out.println(Arrays.toString(curr));
//            System.out.println(Arrays.toString(target));
            curr[ch1]--;
            curr[ch2]++;
//            System.out.println(Arrays.toString(curr));
//            System.out.println(Arrays.toString(target));
//            System.out.println();
            diff += Math.abs(target[ch1] - curr[ch1]);
            diff += Math.abs(target[ch2] - curr[ch2]);
            if (diff == 0)
                ans.add(i);
        }

        return ans;
    }
}
